package org.mics.lang.hash;

import java.util.Collection;
import java.util.HashSet;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;
/**
 * 一致性hash
 * @author mics
 * @date 2022-8-19
 * @version  1.0
 */
public class ConsistentHash<T> {
	
	/**
	 * hash方法
	 */
	private final HashFunction hashFunction;
	
	/**
	 * 虚拟节点
	 */
    private final int numberOfReplicas;  
    
    /**
     * 用来存储虚拟节点hash值 到真实node的映射
     */
    private final SortedMap<Long, T> circle = new TreeMap<Long, T>();  

    public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection<T> nodes) {
        this.hashFunction = hashFunction;
        this.numberOfReplicas = numberOfReplicas;
        for (T node : nodes) {
            add(node);
        }
    }

    /**
     * 增加节点到hash环中
     * @author mics
     * @date 2022-8-19
     * @version  1.0
     * @param node 节点
     */
    public void add(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.put(hashFunction.hash(node.toString() + i), node); 
        }
    }
    
    /**
     * 从hash环中删除节点
     * @author mics
     * @date 2022-8-19
     * @version  1.0
     * @param node 节点
     */
    public void remove(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.remove(hashFunction.hash(node.toString() + i));
        }
    }

    /**
     * 获得一个最近的顺时针节点
     * @param key 为给定键取Hash，取得顺时针方向上最近的一个虚拟节点对应的实际节点
     * @return
     */
    public T get(Object key) {
        if (circle.isEmpty()) {
            return null;
        }
        long hash = hashFunction.hash((String) key);
        if (!circle.containsKey(hash)) {
        	//返回此映射的部分视图，其键大于等于 hash
            SortedMap<Long, T> tailMap = circle.tailMap(hash); 
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }
    
    /**
     * 虚拟节点环节点数量
     * @author mics
     * @date 2022-8-19
     * @version  1.0
     * @return
     */
    public long getSize() {
        return circle.size();
    }
    
    
    public static void main(String[] args) {
        Set<String> nodes = new HashSet<String>();
        nodes.add("1");
        nodes.add("2");
        nodes.add("3");
        ConsistentHash<String> consistentHash = new ConsistentHash<String>(new HashFunction(), 160, nodes);
        System.out.println(consistentHash.get("1.jpg"));
        System.out.println(consistentHash.get("2.jpg"));
        System.out.println(consistentHash.get("3.jpg"));
        System.out.println(consistentHash.get("4.jpg"));
        System.out.println(consistentHash.get("5.jpg"));
        System.out.println(consistentHash.get("6.jpg"));
        System.out.println(consistentHash.get("7.jpg"));
        System.out.println(consistentHash.get("8.jpg"));
        System.out.println(consistentHash.get("9.jpg"));
        System.out.println(consistentHash.get("10.jpg"));
    }

}
